//统计一个数字在排序数组中出现的次数。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 8
//输出: 2 
//
// 示例 2: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 6
//输出: 0 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// 
//
// 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-
//position-of-element-in-sorted-array/ 
//
// Related Topics 数组 二分查找 👍 419 👎 0


package com.leetcode.editor.cn;

public class PJianZhiOffer53IZaiPaiXuShuZuZhongChaZhaoShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new PJianZhiOffer53IZaiPaiXuShuZuZhongChaZhaoShuZiLcof().new Solution();
        int[] arr = {5, 7, 7, 8, 8, 10};
        System.out.println(solution.search(arr, 8));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int search(int[] nums, int target) {
            if (nums == null || nums.length == 0) return 0;
            int count = 0;
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = (right + left) / 2;
                if (nums[mid] == target) {
                    count++;
                    for (int i = mid + 1; i <= right; i++) {
                        if (nums[i] == target) {
                            count++;
                        } else {
                            break;
                        }
                    }
                    for (int i = mid - 1; i >= left; i--) {
                        if (nums[i] == target) {
                            count++;
                        } else {
                            break;
                        }
                    }
                    break;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}